package Tree;

/**
 * 124.二叉树的最大路径和
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 */
public class maxPathSum {
    /**
     * hot100一刷
     */
    class Solution {
        private int maxSum = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            // 递归辅助函数，会在过程中更新maxSum
            getMaxGain(root);
            return maxSum;
        }

        private int getMaxGain(TreeNode node) {
            if (node == null) {
                return 0;
            }
            // 计算左右子树的最大贡献值，若贡献值小于0则置为0（不选取该子树）
            int leftGain = Math.max(getMaxGain(node.left), 0);
            int rightGain = Math.max(getMaxGain(node.right), 0);

            // 当节点node作为“路径根”时，该路径和 = 节点值 + 左贡献 + 右贡献
            int pathSum = node.val + leftGain + rightGain;

            // 更新全局最大值
            maxSum = Math.max(maxSum, pathSum);

            // 返回节点node所在路径能继续向上贡献的最大值
            return node.val + Math.max(leftGain, rightGain);
        }
    }


    /**
     * hot100二刷
     */
    class S {
        int res = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            inorder(root);
            return res;
        }

        public int inorder(TreeNode root) {
            if (root == null)
                return 0;
            int l = Math.max(inorder(root.left), 0);
            int r = Math.max(inorder(root.right), 0);
            res = Math.max(res, root.val + l + r);
            return Math.max(l, r) + root.val;
        }
    }
}
